Aaron Sidford

Monday, October 7, 2013
4:00pm 5130 Upson Hall

Abstract:

In this talk, I will describe a new framework for approximately solving flow problems in capacitated, undirected graphs and I will show how to use this framework to achieve faster asymptotic running times for solving the maximum s-t flow and maximum concurrent multicommodity flow problems. For graphs with n vertices and m edges, I will present an algorithm for computing an epsilon-approximate maximum s-t flow in time O(m^{1+o(1)} epsilon^{-2}), improving on the previous best bound of tilde{O}(mn^{1/3}poly(1/epsilon)), and I will discuss how to compute an epsilon-approximate maximum concurrent multicommodity flow problem with k commodities in O(m^{1+o(1)}epsilon^{-2}k^2) time, improving on the existing bound of \tilde{O}(m^{4/3} poly(k,1/epsilon). In describing these algorithms, I will discuss several new technical tools that may be of independent interest:

 - a non-Euclidean generalization of gradient descent, bounds on its performance, and a way to use this to reduce approximate maximum flow and maximum concurrent flow to oblivious routing;

 - the definition and efficient construction of a new type of flow sparsifier that ameliorates the longstanding gap between the algorithmic efficacy of sparsification on flow and cut problems; and

 - the first almost-linear-time construction of an O(m^{o(1)})-competitive oblivious routing scheme.

This is joint work with Jonathan Kelner, Lorenzo Orecchia, and Yin Tat Lee.